/*************************************************************************
 * File Name:    3Sum_Closest.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-8 20:54:54
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: 3Sum Closest
 |
 | Given an array S of n integers, find three integers in S such that the sum
 | is closest to a given number, target. Return the sum of the three integers.
 | You may assume that each input would have exactly one solution.
 |
 | For example, given array S = {-1 2 1 -4}, and target = 1.
 |
 | The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target)
    {
        sort(num.begin(), num.end());
        int ans, ans_min = INT_MAX;
        int left, right, t;
        
        for (size_t i = 0; i < num.size(); ++i) {
            left = i + 1, right = num.size() - 1;
            while (left < right) {
                t = num[i] + num[left] + num[right] - target;
                
                if (ans_min > abs(t)) {
                    ans_min = abs(t);
                    ans = t + target;
                }
                if (ans_min == 0) return ans;
                if (t < 0) ++left;
                else --right;
            }
        }
        return ans;
    }
};

